package 华为OD机试真题2023.进阶题;

import utils.MyUtil;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class HJ21_上班之路 {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner in = new Scanner(new File("src/main/java/华为OD机试真题2023/进阶题/input/21.txt"));
        MyUtil.START();
        Solution(in);
        //        Solution2(in); //该答案没满分，只有170
        MyUtil.END();
    }

    static int row, column;
    static boolean result = false;

    static void Solution(Scanner in) {
        int T = in.nextInt();
        int C = in.nextInt();
        row = in.nextInt();
        column = in.nextInt();
        in.nextLine(); // 吸收回车
        char[][] matrix = new char[row][column];
        for (int i = 0; i < row; i++) {
            String s = in.nextLine();
            for (int j = 0; j < column; j++) {
                char a = s.charAt(j);
                matrix[i][j] = a;
            }
        }
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                if (matrix[i][j] == 'S') {
                    dfs(matrix, '0', '0', i, j, T, C);
                    if (result) {
                        System.out.println("YES");
                    } else {
                        System.out.println("NO");
                    }
                    return;
                }
            }
        }
    }

    static void dfs(
            char[][] matrix,
            char directionNow,
            char directionBefore,
            int x,
            int y,
            int turn,
            int luzhang) {
        if (result) {
            return;
        }
        if (x < 0 || x >= row || y < 0 || y >= column || turn < 0 || luzhang < 0) {
            return;
        }
        if (matrix[x][y] == 'T') {
            result = true;
            return;
        }
        int TURN = turn;
        int LUZHANG = luzhang;
        char DIRECTIONBEFORE = directionNow;
        if (matrix[x][y] == '*') {
            LUZHANG--;
        }
        if (directionBefore != '0' && directionNow != directionBefore) {
            TURN--;
        }
        dfs(matrix, 'W', DIRECTIONBEFORE, x - 1, y, TURN, LUZHANG); // 上
        dfs(matrix, 'S', DIRECTIONBEFORE, x + 1, y, TURN, LUZHANG); // 上
        dfs(matrix, 'A', DIRECTIONBEFORE, x, y - 1, TURN, LUZHANG); // 上
        dfs(matrix, 'D', DIRECTIONBEFORE, x, y + 1, TURN, LUZHANG); // 上
    }

    static int jR = 0;
    static int jL = 0;
    static int gR = 0;
    static int gL = 0;
    static int row2 = 0;
    static int col = 0;

    static void Solution2(Scanner in) {
        int yW = in.nextInt();
        int yZ = in.nextInt();
        row2 = in.nextInt();
        col = in.nextInt();
        char[][] lu = new char[row2][col];
        for (int i = 0; i < row2; i++) {
            String str = in.next();
            for (int j = 0; j < col; j++) {
                lu[i][j] = str.charAt(j);
                if (lu[i][j] == 'S') {
                    jR = i;
                    jL = j;
                } else if (lu[i][j] == 'T') {
                    gR = i;
                    gL = j;
                }
            }
        }
        int[][] nWs = new int[row2][col];
        int[][] nZs = new int[row2][col];
        boolean[][] states = new boolean[row2][col];
        if (find(yW, yZ, lu, gR, gL, nWs, nZs, states, 0)) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }

    public static boolean find(
            int yW,
            int yZ,
            char[][] lu,
            int nowR,
            int nowL,
            int[][] nWs,
            int[][] nZs,
            boolean[][] states,
            int lastFX) {
        if (0 > nowR || nowR >= nWs.length) {
            return false;
        }
        if (0 > nowL || nowL >= nWs[0].length) {
            return false;
        }
        if (states[nowR][nowL]) {
            return false;
        }
        states[nowR][nowL] = true;
        char c = lu[nowR][nowL];
        if (c == '*') {
            yZ -= 1;
        }
        if (yW < 0 || yZ < 0) {
            return false;
        }
        if ('S' == c) {
            return true;
        }
        int shangR = nowR - 1;
        int xiaR = nowR + 1;
        int zuoL = nowL - 1;
        int youL = nowL + 1;
        boolean f = false;
        // 上
        int nR = shangR;
        int nL = nowL;
        if (2 != lastFX) {
            if (0 == lastFX || 1 == lastFX) {
                f = find(yW, yZ, lu, nR, nL, nWs, nZs, states, 1);
            } else {
                f = find(yW - 1, yZ, lu, nR, nL, nWs, nZs, states, 1);
            }
        }
        if (f) {
            return true;
        }
        // 下
        nR = xiaR;
        nL = nowL;
        if (1 != lastFX) {
            if (0 == lastFX || 2 == lastFX) {
                f = find(yW, yZ, lu, nR, nL, nWs, nZs, states, 2);
            } else {
                f = find(yW - 1, yZ, lu, nR, nL, nWs, nZs, states, 2);
            }
            if (f) {
                return true;
            }
        }
        // 左
        nR = nowR;
        nL = zuoL;
        if (4 != lastFX) {
            if (0 == lastFX || 3 == lastFX) {
                f = find(yW, yZ, lu, nR, nL, nWs, nZs, states, 3);
            } else {
                f = find(yW - 1, yZ, lu, nR, nL, nWs, nZs, states, 3);
            }
        }
        if (f) {
            return true;
        }
        // 右
        nR = nowR;
        nL = youL;
        if (3 != lastFX) {
            if (0 == lastFX || 4 == lastFX) {
                f = find(yW, yZ, lu, nR, nL, nWs, nZs, states, 4);
            } else {
                f = find(yW - 1, yZ, lu, nR, nL, nWs, nZs, states, 4);
            }
        }
        return f;
    }
}
